package listbyorder.access401_500.test480;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/8/20 15:31
 */
public class Solution {

    public static void main(String[] args) {
        int[] arr = {1, 3, -1, -3, 5, 3, 6, 7};
        double[] res = medianSlidingWindow(arr, 3);
    }

    public static double[] medianSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0 || k > nums.length) return null;
        int n = nums.length;
        double[] res = new double[n - k + 1];
        // 创建一个优先级队列
        ArrayList<Integer> list = new ArrayList<Integer>();
        int c = 0;
        int index = 0;
        for (; c < k; c++) {
            list.add(nums[c]);
        }
        while (c < n) {
            res[index++] = cal(list, k);
            list.add(nums[c]);
            list.remove(nums[c - k]);
            c++;
        }
        res[index++] = cal(list, k);
        return res;
    }

    // 获取当前的中位数
    private static double cal(ArrayList<Integer> list, int k) {
        Collections.sort(list);
        if ((k & 1) == 1) {
            return (double) list.get(k / 2);
        } else {
            return (list.get((k / 2) - 1) + list.get(k / 2)) / 2.0;
        }
    }

}
